package com.soulless.array;

/**
 * @author zenglei
 * @Description 功能描述    有序数组和二分查找
 * 1. 在一个查询区间中间，确定区间中间的下，(length - 1) / 2 = 中间下标
 * 2. 查找数跟中心下标的值比较。
 * 查找数=中心数，则找到。
 * 查找数>中心数，在中心下标后的区间中重复步骤1、2。
 * 查找数<中心数，在中心下标前的区间中重复步骤1、2。
 * @date 2020/11/21 14:47
 */
public class BinarySearch {

    public int[] arr = {1, 4, 7, 8, 10, 15, 26, 33, 55, 57, 60};
    public int currIndex;


    /**
     * @desription TODO
     * @param value 查找的值
     * @param start
     * @param end
     * @return {@link int}  查找到的下标
     * @throws
     * @author zenglei
     * @date 2020/11/21 14:53
     */
    public int binSearch(int value, int start, int end) {
        currIndex = end / 2 + start;
        if (arr[currIndex] == value) {
            return currIndex;
        }
        if (start >= end) {
            return -1;
        }
        if (arr[currIndex] < value) {
            return binSearch(value, currIndex + 1, end);
        }
        if (arr[currIndex] > value) {
            return  binSearch(value, start, currIndex - 1);
        }
        return -1;
    }
}

class Test{
    public static void main(String[] args) {
        BinarySearch bs = new BinarySearch();
        int index = bs.binSearch(15, 0, bs.arr.length - 1);
        System.out.println("============== index ===========  " + index);
    }
}
